package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/1 15:36
 */
public class AC861二分图的最大匹配 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n1 = Integer.parseInt(s[0]), n2 = Integer.parseInt(s[1]), m = Integer.parseInt(s[2]);
        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split(" ");
            int u = Integer.parseInt(s[0]), v = Integer.parseInt(s[1]);
            edges[i][0] = u;
            edges[i][1] = v;
        }
        writer.write(hungary(n1, n2, edges) + "\n");
        writer.flush();
    }

    private static int hungary(int n1, int n2, int[][] edges) {
        int m = edges.length, index = 0, answer = 0;
        int[] head = new int[n1 + 1], element = new int[m], next = new int[m], match = new int[n2 + 1];
        for (int i = 1; i <= n1; i++) head[i] = -1;
        for (int[] edge : edges) {
            element[index] = edge[1];
            next[index] = head[edge[0]];
            head[edge[0]] = index++;
        }
        boolean[] visited = new boolean[n2 + 1];
        //尝试对每一个结点都进行匹配
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) visited[j] = false;
            if (dfs(head, element, next, match, visited, i)) answer++;
        }
        return answer;
    }

    private static boolean dfs(int[] head, int[] element, int[] next, int[] match, boolean[] visited, int u) {
        for (int i = head[u]; i != -1; i = next[i]) {
            int v = element[i];
            //不能反复的尝试匹配v结点
            if (visited[v]) continue;
            visited[v] = true;
            //查看v结点是否已经有匹配的结点，如果已经匹配了，尝试给match[v]重新匹配一个结点
            if (match[v] == 0 || dfs(head, element, next, match, visited, match[v])) {
                //给match[v]匹配成功，当前结点u和v匹配
                match[v] = u;
                return true;
            }
        }
        return false;
    }
}
